Pagina principala | Inscriere | Autentificare | Probleme | Runde | Clasament | Anunturi | Echipa | Regulament | Exit


Vizualizare problema: string

Titlul problemei string
Grupa Grupa B
Problema numarul 2
Runda numarul 12
Timp de executie (ms) 2000
Punctaj maxim pentru problema 50
Dimensiunea maxima a segmentului de date (MB) 15
Dimensiunea maxima a stivei (MB) 1
Profesorul care a propus problema Mugurel Andreica
Enuntul problemei
Se considera alfabetul format numai din literele mici ‘a’ si ‘b’ si un sir S format
numai din caractere din acest alfabet. Pe acest alfabet, se defineste relatia de incluziune, astfel: un
sir S1 este inclus în sirul S2, daca lungimea sirului S2 (egala cu numarul de caractere ale sirului)
este mai mare sau egala decât a sirului S1 si exista o pozitie k în sirul S2, astfel încât
S2[k]=S1[1],S2[k+1]=S1[2], .. , S2[k+L-1]=S1[L], unde L este lungimea sirului S1,
k+L-1 este mai mic sau egal decât lungimea sirului S2, iar X[i] reprezinta al i-lea caracter din
sirul X. De exemplu, sirul ‘abba’ este inclus în sirul ‘babbaba’, dar nu este inclus în sirul
‘ababab’.

Cerinta
Determinati cel mai scurt sir format numai din caractere din alfabetul considerat, care sa
nu fie inclus în sirul S.

Date de intrare
Pe prima linie a fisierului de intrare string.in se afla numarul întreg N, reprezentând
numarul de caractere ale sirului S. Pe urmatoarea linie se afla cele N caractere, în ordinea pozitiei
lor în sir.

Date de iesire
Pe prima linie a fisierului de iesire string.out veti afisa numarul întreg L,
reprezentând lungimea minima a unui sir care nu este inclus în sirul S. Pe a doua linie veti afisa
un astfel de sir. Daca exista mai multe solutii, puteti afisa oricare dintre ele.

Restrictii si precizari:
1 <= N <= 500 000
L > 0

Exemplu

string.in
11
aabaaabbbab

string.out
4
aaaa



Click aici pentru a va intoarce

© 2002 Vâlsan Mihai Liviu
Puteti trimite intrebari, comentarii, sau sugestii la adresa liviuvalsan@yahoo.com